package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.LinkedList;

/**
 * @author: ZhouBert
 * @date: 2021/3/3
 * @description: 剑指 Offer 26. 树的子结构
 * https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
 */
public class B_剑指Offer26_树的子结构 {

	static B_剑指Offer26_树的子结构 action = new B_剑指Offer26_树的子结构();

	public static void main(String[] args) {
//		test1();
//		test2();
		test3();
	}

	public static void test1() {
		TreeNode A = TreeNode.stringToTreeNode("[1,2,3,4]");
		TreeNode B = TreeNode.stringToTreeNode("[3]");
		boolean res = action.isSubStructureByRecursive(A, B);
		System.out.println("res = " + res);
	}

	public static void test2() {
		TreeNode A = TreeNode.stringToTreeNode("[3,4,5,1,2]");
		TreeNode B = TreeNode.stringToTreeNode("[4,1]");
		boolean res = action.isSubStructureByRecursive(A, B);
		System.out.println("res = " + res);
	}

	public static void test3() {
		TreeNode A = TreeNode.stringToTreeNode("[10,12,6,8,3,11]");
		TreeNode B = TreeNode.stringToTreeNode("[10,12,6,8]");
		boolean res = action.isSubStructureByRecursive(A, B);
		System.out.println("res = " + res);
	}

	/**
	 * 可以明确这是一个遍历问题，那么哪种遍历最适合呢？
	 * 应该是 根-左-右 先序遍历！
	 * 如果题目木有苛刻的要求，那么就将 A 遍历保存进 list ,然后将 B 的根节点去遍历 list
	 * 判断是否重叠（如果节点缺少，需要记录 null ,如果将 B 也记录到 list 会更方便一点）
	 * --
	 * 这个有个BUG 木有考虑到：当节点不是根据先序遍历的顺序重合的时候，就会直接返回  false
	 * 无法分辨！
	 * @param A
	 * @param B
	 * @return
	 */
	public boolean isSubStructureFail(TreeNode A, TreeNode B) {
		if (B == null || A == null) {
			return false;
		}
		LinkedList<TreeNode> listA = new LinkedList<>();
		preOrder(A, listA);

		LinkedList<TreeNode> listB = new LinkedList<>();
		preOrder(B, listB);
		//将 listB 的末尾去除 null
		while (listB.peekLast() == null) {
			listB.removeLast();
		}

		int lenB = listB.size();

		int indexA = 0, indexB = 0;
		int lenA = listA.size();
		int endAIndex = lenA - 1;

		TreeNode curA = listA.get(indexA);
		TreeNode curB = listB.get(indexB);
		boolean isMatch = false;
		while (indexA < endAIndex) {
			if (curB == null) {
				if (curA != null) {
					if (isMatch) {
						//如果是在匹配中，重新匹配
						indexB = 0;
						curB = listB.get(indexB);
					}
					curA = listA.get(++indexA);
					isMatch = false;
				} else {
					//如果匹配到了
					curA = listA.get(++indexA);
					if (++indexB == lenB) {
						return true;
					}
					curB = listB.get(indexB);
					if (isMatch) {

					} else {
						isMatch = true;
					}
				}
			} else {
				if (curA == null || curA.val != curB.val) {
					if (isMatch) {
						//如果是在匹配中，重新匹配
						indexB = 0;
						curB = listB.get(indexB);
					}
					curA = listA.get(++indexA);
					isMatch = false;
				} else {
					//如果匹配到了
					curA = listA.get(++indexA);
					if (++indexB == lenB) {
						return true;
					}
					curB = listB.get(indexB);
					if (isMatch) {

					} else {
						isMatch = true;
					}
				}
			}
		}
		if (isMatch && indexB == lenB - 1) {
			//此时已经匹配
			if (curB == null) {
				if (curA == null) {
					return true;
				} else {
					return false;
				}
			} else {
				if (curA == null || curA.val != curB.val) {
					return false;
				} else {
					return true;
				}
			}

		}

		return false;
	}


	/**
	 * 通过递归的方式完成
	 * 看了下题解，发现只能让指针移动的轨迹完全相同时，便能找到结果
	 * @param A
	 * @param B
	 * @return
	 */
	public boolean isSubStructureByRecursive(TreeNode A, TreeNode B){
		if(A == null || B == null) return false;
		return dfs(A, B) || isSubStructureByRecursive(A.left, B) || isSubStructureByRecursive(A.right, B);
	}

	private boolean dfs(TreeNode A, TreeNode B) {
		if(B == null) return true;
		if(A == null) return false;
		return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
	}

	/**
	 * 先序遍历 并存入 list
	 *
	 * @param root
	 * @param list
	 */
	private void preOrder(TreeNode root, LinkedList<TreeNode> list) {
		list.add(root);
		if (root == null) {
			return;
		}
		preOrder(root.left, list);
		preOrder(root.right, list);
	}


}
